1. Field of the Invention
The invention relates to a method and a device for generating a random number by means of a linear feedback shift register, in particular for generating a random number in a transponder.
2. Description of the Background Art
Random numbers are used for encryption, for example. Along with the algorithm used, the length and statistical properties of the random number used are extremely important for the quality of the encryption. Many attacks for decrypting an encrypted text are targeted at random number generation. Thus, certain requirements are placed on random numbers, such as high periodicity, uniform distribution of the random numbers over the value range, uniform distribution of zeroes and ones, the probability of runs of ones or zeroes, and/or low correlation of one random number to a subsequent random number. The methods for generating the random number must typically be disclosed. For this reason, it is also important that different random numbers are produced under identical boundary conditions reproducible by an attacker.
Encryption by means of random numbers has applications in contactless identification systems or what are known as radio frequency identification (RFID) systems, for example. Such systems typically include a base station or a reader unit and a number of transponders or remote sensors that are simultaneously located in the base station's response area. The transponders or their transmitting and receiving devices typically do not have an active transmitter for transmitting data to the base station. Such non-active systems are called passive systems when they do not have their own power supply, and are called semipassive systems when they have their own power supply. Passive transponders take the energy required to supply them from the electromagnetic field emitted by the base station. A variety of standards exist for RFID systems. These include the standards developed by EPCglobal Inc. for uniform use of RFID technologies. For example, according to the EPCglobal class 1, generation 2 protocol, a password with a length of 32 bits must be cracked in order to obtain write access to a memory area of a transponder. Transmission of this password, at least in the forward link, which is to say from a base station to a transponder, is protected by a 16-bitwise XOR encryption of the password with a random number that is provided to the base station by the transponder. The transponder must therefore have means for generating a random number.
Through the use of passive transponders, additional requirements are placed on generation of a random number in a transponder besides a high quality of the random number, for example components that are used must be integratable in the smallest possible area, and power consumption must be minimized. In passive transponders, the power consumption is correlated with the communication distance, whereby the communication distance increases as the power consumption of the transponder decrease. Preferably, it is desired to use existing switching components to reduce the area of the surface.
So-called linear feedback shift registers (LFSR) are known for generating pseudorandom numbers with good uniformity of distribution and minimal autocorrelation. The longer a linear feedback shift register is selected, the longer its periodicity is and the quality of the pseudo random number. However, because of high power consumption and a large area requirement, long linear feedback shift registers are generally impractical for generating random numbers in passive transponders. Moreover, a result of a linear feedback shift register is in principle predictable and thus reproducible because of its synchronous, digital properties, even when a feedback polynomial is changed.
In order to reduce predictability of a shift register, it is also known to use two oscillators with different frequencies. In this context, one oscillator with a slow frequency is used as the clock frequency for the shift register. In addition, a second oscillator with a higher frequency is used as the data input for the shift register. However, one disadvantage of this solution is that the second oscillator with the higher frequency also has a higher power consumption. Moreover, the frequencies must be very closely matched to one another to prevent runs of zeroes or ones at the data input. Such precision is accompanied by a high power consumption, however.
In addition, it is known to store specific random numbers in a memory area of a device, such as a computer, a transponder, or the like; said random numbers can either be read out directly as the random number or can be used as so-called seeds for a shift register. However, these stored random numbers must be protected by appropriate mechanisms to prevent undesired readout by an attacker. Moreover, the memory required to store random numbers generated in such a manner must also be taken into account. Such memory areas are preferably permanent memories such as ROM or EEPROMS. Disadvantageous though is that thereby the memory area and the power consumption is increased, in particular because a high number of random numbers must be stored there.
Known from WO 99/38069 are a method and a device for generating random numbers, wherein a linear feedback shift register is connected to a not entirely ideal physical noise source. To this end, a random data stream is generated by the physical noise source, and this data stream is combined with a second data stream generated by the linear feedback shift register in such a manner that a nearly ideal uniform distribution of ones and zeroes results. An addition method and/or an XOR method are cited as examples of combining methods. Noise sources or noise generators, including the linear feedback shift register.